package com.tgy.algorithm.base;

import java.util.Arrays;

public class _快速排序 {

    public static void quickSort(int[] nums) {

        doQuickSort(nums,0,  nums.length-1);
    }

    public static void doQuickSort(int[] nums, int left, int right) {

        if(left >= right) {
            return;
        }

        int pivot = nums[right];
        int preIndex = left - 1;
        int start = left;

        // 3,4,2,3,2
        // 2,4,3,3 ,2
        while (start < right) {
            if(nums[start] <= pivot) {
                if(preIndex + 1 != start) {
                    swap(nums, preIndex + 1, start);
                }
                preIndex++;
            }
            start++;
        }

        swap(nums, preIndex + 1, right);
        doQuickSort(nums,left,preIndex);
        doQuickSort(nums,preIndex + 2,right);
    }

    // 3,2,4,2,3,2
    // 2,3,4,2,3,2
    // 2,2,4,3,3,2

    // 交换两个数
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[maxSize];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    public static void helandSort(int[] nums,int left,int right) {

        if (nums == null || nums.length < 2) {
            return;
        }

        int pivot = nums[right];
        int preIndex = left - 1;
        int index = left;
        int endIndex = right - 1;

        while (index <= endIndex) {
            if (nums[index] < pivot) {
                if(preIndex + 1 != index) {
                    swap(nums, preIndex + 1, index);
                }
                preIndex++;
                index++;
            }else if(nums[index] == pivot) {
                index++;
            }else {
                // 大于pivot
                swap(nums, index, endIndex);
                endIndex--;
            }
        }
    }

    public static void helandSort01(int[] nums,int left,int right) {

        if (left >= right) {
            return;
        }

        int preIndex = left - 1;
        int index = left;
        int pivot = nums[right];
        int postIndex = right - 1;

        while (index <= postIndex) {
            if (nums[index] < pivot) {
                if (preIndex + 1 != index) {
                    swap(nums, preIndex + 1, index);
                }
                preIndex++;
                index++;
            }else if(nums[index] == pivot) {
                index++;
            }else  {
                swap(nums, index, postIndex--);
            }
        }
        // 交换最后一个元素与preIndex + 1的值
        swap(nums, postIndex+1, right);
    }

    public static void main(String[] args) {
//        int[] nums = new int[] {3,4,2,3,2};
//        quickSort(nums);
//        System.out.println(Arrays.toString(nums));
//        int[] nums = generateRandomArray(10, 10);
//        System.out.println(Arrays.toString(nums));
//        quickSort(nums);
//        System.out.println(Arrays.toString(nums));
        int[] nums = new int[] {3,1,4,5,1,3,2};
        helandSort01(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }
}
